package java_cup;

import java.util.Hashtable;
import java.util.Enumeration;

/**
 * This class represents a production in the grammar. It contains a LHS non
 * terminal, and an array of RHS symbols. As various transformations are done on
 * the RHS of the production, it may shrink. As a result a separate length is
 * always maintained to indicate how much of the RHS array is still valid.
 * <p>
 * 
 * I addition to construction and manipulation operations, productions provide
 * methods for factoring out actions (see remove_embedded_actions()), for
 * computing the nullability of the production (i.e., can it derive the empty
 * string, see check_nullable()), and operations for computing its first set
 * (i.e., the set of terminals that could appear at the beginning of some string
 * derived from the production, see check_first_set()).
 * 
 * @see java_cup.production_part
 * @see java_cup.symbol_part
 * @see java_cup.action_part
 * @version last updated: 7/3/96
 * @author Frank Flannery
 */

public class production {

	/*-----------------------------------------------------------*/
	/*--- Constructor(s) ----------------------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Full constructor. This constructor accepts a LHS non terminal, an array
	 * of RHS parts (including terminals, non terminals, and actions), and a
	 * string for a final reduce action. It does several manipulations in the
	 * process of creating a production object. After some validity checking it
	 * translates labels that appear in actions into code for accessing objects
	 * on the runtime parse stack. It them merges adjacent actions if they
	 * appear and moves any trailing action into the final reduce actions
	 * string. Next it removes any embedded actions by factoring them out with
	 * new action productions. Finally it assigns a unique index to the
	 * production.
	 * <p>
	 * 
	 * Factoring out of actions is accomplished by creating new "hidden" non
	 * terminals. For example if the production was originally:
	 * 
	 * <pre>
	 *    A ::= B {action} C D
	 * </pre>
	 * 
	 * then it is factored into two productions:
	 * 
	 * <pre>
	 *    A ::= B X C D
	 *    X ::= {action}
	 * </pre>
	 * 
	 * (where X is a unique new non terminal). This has the effect of placing
	 * all actions at the end where they can be handled as part of a reduce by
	 * the parser.
	 */
	public production(non_terminal lhs_sym, production_part rhs_parts[],
			int rhs_l, String action_str) throws internal_error {
		int i;
		action_part tail_action;
		String declare_str;
		int rightlen = rhs_l;

		/* remember the length */
		if (rhs_l >= 0)
			_rhs_length = rhs_l;
		else if (rhs_parts != null)
			_rhs_length = rhs_parts.length;
		else
			_rhs_length = 0;

		/* make sure we have a valid left-hand-side */
		if (lhs_sym == null)
			throw new internal_error(
					"Attempt to construct a production with a null LHS");

		/*
		 * I'm not translating labels anymore, I'm adding code to declare labels
		 * as valid variables. This way, the users code string is untouched 6/96
		 * frankf
		 */

		/*
		 * check if the last part of the right hand side is an action. If it is,
		 * it won't be on the stack, so we don't want to count it in the
		 * rightlen. Then when we search down the stack for a Symbol, we don't
		 * try to search past action
		 */

		if (rhs_l > 0) {
			if (rhs_parts[rhs_l - 1].is_action()) {
				rightlen = rhs_l - 1;
			} else {
				rightlen = rhs_l;
			}
		}

		/* get the generated declaration code for the necessary labels. */
		declare_str = declare_labels(rhs_parts, rightlen, action_str);

		if (action_str == null)
			action_str = declare_str;
		else
			action_str = declare_str + action_str;

		/* count use of lhs */
		lhs_sym.note_use();

		/* create the part for left-hand-side */
		_lhs = new symbol_part(lhs_sym);

		/* merge adjacent actions (if any) */
		_rhs_length = merge_adjacent_actions(rhs_parts, _rhs_length);

		/* strip off any trailing action */
		tail_action = strip_trailing_action(rhs_parts, _rhs_length);
		if (tail_action != null)
			_rhs_length--;

		/*
		 * Why does this run through the right hand side happen over and over?
		 * here a quick combination of two prior runs plus one I wanted of my
		 * own frankf 6/25/96
		 */
		/* allocate and copy over the right-hand-side */
		/* count use of each rhs symbol */
		_rhs = new production_part[_rhs_length];
		for (i = 0; i < _rhs_length; i++) {
			_rhs[i] = rhs_parts[i];
			if (!_rhs[i].is_action()) {
				((symbol_part) _rhs[i]).the_symbol().note_use();
				if (((symbol_part) _rhs[i]).the_symbol() instanceof terminal) {
					_rhs_prec = ((terminal) ((symbol_part) _rhs[i])
							.the_symbol()).precedence_num();
					_rhs_assoc = ((terminal) ((symbol_part) _rhs[i])
							.the_symbol()).precedence_side();
				}
			}
		}

		/*
		 * now action string is really declaration string, so put it in front!
		 * 6/14/96 frankf
		 */
		if (action_str == null)
			action_str = "";
		if (tail_action != null && tail_action.code_string() != null)
			action_str = action_str + "\t\t" + tail_action.code_string();

		/* stash the action */
		_action = new action_part(action_str);

		/* rewrite production to remove any embedded actions */
		remove_embedded_actions();

		/* assign an index */
		_index = next_index++;

		/* put us in the global collection of productions */
		_all.put(new Integer(_index), this);

		/* put us in the production list of the lhs non terminal */
		lhs_sym.add_production(this);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Constructor with no action string. */
	public production(non_terminal lhs_sym, production_part rhs_parts[],
			int rhs_l) throws internal_error {
		this(lhs_sym, rhs_parts, rhs_l, null);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/*
	 * Constructor with precedence and associativity of production contextually
	 * define
	 */
	public production(non_terminal lhs_sym, production_part rhs_parts[],
			int rhs_l, String action_str, int prec_num, int prec_side)
			throws internal_error {
		this(lhs_sym, rhs_parts, rhs_l, action_str);

		/* set the precedence */
		set_precedence_num(prec_num);
		set_precedence_side(prec_side);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/*
	 * Constructor w/ no action string and contextual precedence defined
	 */
	public production(non_terminal lhs_sym, production_part rhs_parts[],
			int rhs_l, int prec_num, int prec_side) throws internal_error {
		this(lhs_sym, rhs_parts, rhs_l, null);
		/* set the precedence */
		set_precedence_num(prec_num);
		set_precedence_side(prec_side);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/*-----------------------------------------------------------*/
	/*--- (Access to) Static (Class) Variables ------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Table of all productions. Elements are stored using their index as the
	 * key.
	 */
	protected static Hashtable _all = new Hashtable();

	/** Access to all productions. */
	public static Enumeration all() {
		return _all.elements();
	}

	/** Lookup a production by index. */
	public static production find(int indx) {
		return (production) _all.get(new Integer(indx));
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Total number of productions. */
	public static int number() {
		return _all.size();
	}

	/** Static counter for assigning unique index numbers. */
	protected static int next_index;

	/*-----------------------------------------------------------*/
	/*--- (Access to) Instance Variables ------------------------*/
	/*-----------------------------------------------------------*/

	/** The left hand side non-terminal. */
	protected symbol_part _lhs;

	/** The left hand side non-terminal. */
	public symbol_part lhs() {
		return _lhs;
	}

	/** The precedence of the rule */
	protected int _rhs_prec = -1;
	protected int _rhs_assoc = -1;

	/** Access to the precedence of the rule */
	public int precedence_num() {
		return _rhs_prec;
	}

	public int precedence_side() {
		return _rhs_assoc;
	}

	/** Setting the precedence of a rule */
	public void set_precedence_num(int prec_num) {
		_rhs_prec = prec_num;
	}

	public void set_precedence_side(int prec_side) {
		_rhs_assoc = prec_side;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** A collection of parts for the right hand side. */
	protected production_part _rhs[];

	/** Access to the collection of parts for the right hand side. */
	public production_part rhs(int indx) throws internal_error {
		if (indx >= 0 && indx < _rhs_length)
			return _rhs[indx];
		else
			throw new internal_error(
					"Index out of range for right hand side of production");
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** How much of the right hand side array we are presently using. */
	protected int _rhs_length;

	/** How much of the right hand side array we are presently using. */
	public int rhs_length() {
		return _rhs_length;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * An action_part containing code for the action to be performed when we
	 * reduce with this production.
	 */
	protected action_part _action;

	/**
	 * An action_part containing code for the action to be performed when we
	 * reduce with this production.
	 */
	public action_part action() {
		return _action;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Index number of the production. */
	protected int _index;

	/** Index number of the production. */
	public int index() {
		return _index;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Count of number of reductions using this production. */
	protected int _num_reductions = 0;

	/** Count of number of reductions using this production. */
	public int num_reductions() {
		return _num_reductions;
	}

	/** Increment the count of reductions with this non-terminal */
	public void note_reduction_use() {
		_num_reductions++;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Is the nullability of the production known or unknown? */
	protected boolean _nullable_known = false;

	/** Is the nullability of the production known or unknown? */
	public boolean nullable_known() {
		return _nullable_known;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Nullability of the production (can it derive the empty string). */
	protected boolean _nullable = false;

	/** Nullability of the production (can it derive the empty string). */
	public boolean nullable() {
		return _nullable;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * First set of the production. This is the set of terminals that could
	 * appear at the front of some string derived from this production.
	 */
	protected terminal_set _first_set = new terminal_set();

	/**
	 * First set of the production. This is the set of terminals that could
	 * appear at the front of some string derived from this production.
	 */
	public terminal_set first_set() {
		return _first_set;
	}

	/*-----------------------------------------------------------*/
	/*--- Static Methods ----------------------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Determine if a given character can be a label id starter.
	 * 
	 * @param c
	 *            the character in question.
	 */
	protected static boolean is_id_start(char c) {
		return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c == '_');

		// later need to handle non-8-bit chars here
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Determine if a character can be in a label id.
	 * 
	 * @param c
	 *            the character in question.
	 */
	protected static boolean is_id_char(char c) {
		return is_id_start(c) || (c >= '0' && c <= '9');
	}

	/*-----------------------------------------------------------*/
	/*--- General Methods ---------------------------------------*/
	/*-----------------------------------------------------------*/

	/**
	 * Return label declaration code
	 * 
	 * @param labelname
	 *            the label name
	 * @param stack_type
	 *            the stack type of label?
	 * @author frankf
	 */
	protected String make_declaration(String labelname, String stack_type,
			int offset) {
		String ret;

		/* Put in the left/right value labels */
		if (emit.lr_values())
			ret = "\t\tint " + labelname + "left = ((java_cup.runtime.Symbol)"
					+ emit.pre("stack") + ".elementAt(" + emit.pre("top") + "-"
					+ offset + ")).left;\n" + "\t\tint " + labelname
					+ "right = ((java_cup.runtime.Symbol)" + emit.pre("stack")
					+ ".elementAt(" + emit.pre("top") + "-" + offset
					+ ")).right;\n";
		else
			ret = "";

		/* otherwise, just declare label. */
		return ret + "\t\t" + stack_type + " " + labelname + " = ("
				+ stack_type + ")((" + "java_cup.runtime.Symbol) "
				+ emit.pre("stack") + ".elementAt(" + emit.pre("top") + "-"
				+ offset + ")).value;\n";

	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Declare label names as valid variables within the action string
	 * 
	 * @param rhs
	 *            array of RHS parts.
	 * @param rhs_len
	 *            how much of rhs to consider valid.
	 * @param final_action
	 *            the final action string of the production.
	 * @param lhs_type
	 *            the object type associated with the LHS symbol.
	 */
	protected String declare_labels(production_part rhs[], int rhs_len,
			String final_action) {
		String declaration = "";

		symbol_part part;
		action_part act_part;
		int pos;

		/* walk down the parts and extract the labels */
		for (pos = 0; pos < rhs_len; pos++) {
			if (!rhs[pos].is_action()) {
				part = (symbol_part) rhs[pos];

				/* if it has a label, make declaration! */
				if (part.label() != null) {
					declaration = declaration
							+ make_declaration(part.label(), part.the_symbol()
									.stack_type(), rhs_len - pos - 1);
				}
			}
		}
		return declaration;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Helper routine to merge adjacent actions in a set of RHS parts
	 * 
	 * @param rhs_parts
	 *            array of RHS parts.
	 * @param len
	 *            amount of that array that is valid.
	 * @return remaining valid length.
	 */
	protected int merge_adjacent_actions(production_part rhs_parts[], int len) {
		int from_loc, to_loc, merge_cnt;

		/* bail out early if we have no work to do */
		if (rhs_parts == null || len == 0)
			return 0;

		merge_cnt = 0;
		to_loc = -1;
		for (from_loc = 0; from_loc < len; from_loc++) {
			/* do we go in the current position or one further */
			if (to_loc < 0 || !rhs_parts[to_loc].is_action()
					|| !rhs_parts[from_loc].is_action()) {
				/* next one */
				to_loc++;

				/* clear the way for it */
				if (to_loc != from_loc)
					rhs_parts[to_loc] = null;
			}

			/* if this is not trivial? */
			if (to_loc != from_loc) {
				/* do we merge or copy? */
				if (rhs_parts[to_loc] != null && rhs_parts[to_loc].is_action()
						&& rhs_parts[from_loc].is_action()) {
					/* merge */
					rhs_parts[to_loc] = new action_part(
							((action_part) rhs_parts[to_loc]).code_string()
									+ ((action_part) rhs_parts[from_loc])
											.code_string());
					merge_cnt++;
				} else {
					/* copy */
					rhs_parts[to_loc] = rhs_parts[from_loc];
				}
			}
		}

		/* return the used length */
		return len - merge_cnt;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Helper routine to strip a trailing action off rhs and return it
	 * 
	 * @param rhs_parts
	 *            array of RHS parts.
	 * @param len
	 *            how many of those are valid.
	 * @return the removed action part.
	 */
	protected action_part strip_trailing_action(production_part rhs_parts[],
			int len) {
		action_part result;

		/* bail out early if we have nothing to do */
		if (rhs_parts == null || len == 0)
			return null;

		/* see if we have a trailing action */
		if (rhs_parts[len - 1].is_action()) {
			/* snip it out and return it */
			result = (action_part) rhs_parts[len - 1];
			rhs_parts[len - 1] = null;
			return result;
		} else
			return null;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Remove all embedded actions from a production by factoring them out into
	 * individual action production using new non terminals. if the original
	 * production was:
	 * 
	 * <pre>
	 *    A ::= B {action1} C {action2} D
	 * </pre>
	 * 
	 * then it will be factored into:
	 * 
	 * <pre>
	 *    A ::= B NT$1 C NT$2 D
	 *    NT$1 ::= {action1}
	 *    NT$2 ::= {action2}
	 * </pre>
	 * 
	 * where NT$1 and NT$2 are new system created non terminals.
	 */

	/*
	 * the declarations added to the parent production are also passed along, as
	 * they should be perfectly valid in this code string, since it was
	 * originally a code string in the parent, not on its own. frank 6/20/96
	 */
	protected void remove_embedded_actions(

	) throws internal_error {
		non_terminal new_nt;
		production new_prod;
		String declare_str;

		/* walk over the production and process each action */
		for (int act_loc = 0; act_loc < rhs_length(); act_loc++)
			if (rhs(act_loc).is_action()) {

				declare_str = declare_labels(_rhs, act_loc, "");
				/* create a new non terminal for the action production */
				new_nt = non_terminal.create_new();
				new_nt.is_embedded_action = true; /* 24-Mar-1998, CSA */

				/* create a new production with just the action */
				new_prod = new action_production(this, new_nt, null, 0,
						declare_str
								+ ((action_part) rhs(act_loc)).code_string());

				/* replace the action with the generated non terminal */
				_rhs[act_loc] = new symbol_part(new_nt);
			}
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Check to see if the production (now) appears to be nullable. A production
	 * is nullable if its RHS could derive the empty string. This results when
	 * the RHS is empty or contains only non terminals which themselves are
	 * nullable.
	 */
	public boolean check_nullable() throws internal_error {
		production_part part;
		symbol sym;
		int pos;

		/* if we already know bail out early */
		if (nullable_known())
			return nullable();

		/* if we have a zero size RHS we are directly nullable */
		if (rhs_length() == 0) {
			/* stash and return the result */
			return set_nullable(true);
		}

		/* otherwise we need to test all of our parts */
		for (pos = 0; pos < rhs_length(); pos++) {
			part = rhs(pos);

			/* only look at non-actions */
			if (!part.is_action()) {
				sym = ((symbol_part) part).the_symbol();

				/* if its a terminal we are definitely not nullable */
				if (!sym.is_non_term())
					return set_nullable(false);
				/* its a non-term, is it marked nullable */
				else if (!((non_terminal) sym).nullable())
					/* this one not (yet) nullable, so we aren't */
					return false;
			}
		}

		/* if we make it here all parts are nullable */
		return set_nullable(true);
	}

	/** set (and return) nullability */
	boolean set_nullable(boolean v) {
		_nullable_known = true;
		_nullable = v;
		return v;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/**
	 * Update (and return) the first set based on current NT firsts. This
	 * assumes that nullability has already been computed for all non terminals
	 * and productions.
	 */
	public terminal_set check_first_set() throws internal_error {
		int part;
		symbol sym;

		/* walk down the right hand side till we get past all nullables */
		for (part = 0; part < rhs_length(); part++) {
			/* only look at non-actions */
			if (!rhs(part).is_action()) {
				sym = ((symbol_part) rhs(part)).the_symbol();

				/* is it a non-terminal? */
				if (sym.is_non_term()) {
					/* add in current firsts from that NT */
					_first_set.add(((non_terminal) sym).first_set());

					/* if its not nullable, we are done */
					if (!((non_terminal) sym).nullable())
						break;
				} else {
					/* its a terminal -- add that to the set */
					_first_set.add((terminal) sym);

					/* we are done */
					break;
				}
			}
		}

		/* return our updated first set */
		return first_set();
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Equality comparison. */
	public boolean equals(production other) {
		if (other == null)
			return false;
		return other._index == _index;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Generic equality comparison. */
	@Override
	public boolean equals(Object other) {
		if (!(other instanceof production))
			return false;
		else
			return equals((production) other);
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Produce a hash code. */
	@Override
	public int hashCode() {
		/* just use a simple function of the index */
		return _index * 13;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Convert to a string. */
	@Override
	public String toString() {
		String result;

		/* catch any internal errors */
		try {
			result = "production [" + index() + "]: ";
			result += ((lhs() != null) ? lhs().toString() : "$$NULL-LHS$$");
			result += " :: = ";
			for (int i = 0; i < rhs_length(); i++)
				result += rhs(i) + " ";
			result += ";";
			if (action() != null && action().code_string() != null)
				result += " {" + action().code_string() + "}";

			if (nullable_known())
				if (nullable())
					result += "[NULLABLE]";
				else
					result += "[NOT NULLABLE]";
		} catch (internal_error e) {
			/*
			 * crash on internal error since we can't throw it from here
			 * (because superclass does not throw anything.
			 */
			e.crash();
			result = null;
		}

		return result;
	}

	/* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */

	/** Convert to a simpler string. */
	public String to_simple_string() throws internal_error {
		String result;

		result = ((lhs() != null) ? lhs().the_symbol().name() : "NULL_LHS");
		result += " ::= ";
		for (int i = 0; i < rhs_length(); i++)
			if (!rhs(i).is_action())
				result += ((symbol_part) rhs(i)).the_symbol().name() + " ";

		return result;
	}

	/*-----------------------------------------------------------*/

}
